/**
 * @file pt_heap5.c
 * @author Linquan  
 * @brief 
 *          1、通过调用 pt_heap_region函数进行初始化，
 *              只有调用该函数后才能允许使用内存分配和释放
 *          2、pt_heap_region_t建立的区域地址顺序要从小到大，
 *             最后要以{NULL，0}结尾(源码是以0做判断结束循环)
 * @version 1.0
 * @date 2024-06-13
 * 
 * @copyright Copyright (c) 2024
 * 
 */


#include "FreeRTOS_heap5.h"
#if  FREE_RTOS_HEAP_5

#include <stdlib.h>

 #include "color_print.h"

// 字节对齐，移植敏感
#define BYTE_ALIGNMENT 8
// 断言，移植敏感
#define HEAP_ASSERT(expr)  ASSERT_PARAM(expr,"request size is not Byte alignment ")

#define BYTE_ALIGNMENT_MASK BYTE_ALIGNMENT - 1

#define MINIMUM_BLOCK_SIZE  ( ( size_t ) ( heap_struct_size << 1 ) )

#define BITS_PER_BYTE         ( ( size_t ) 8 )



typedef struct A_BLOCK_LINK
{
    struct A_BLOCK_LINK * next_free_block; /*<< The next free block in the list. */
    size_t block_size;                     /*<< The size of the free block. */
} block_link_t;

#if USE_MALLOC_FAILED_HOOK
__attribute__((weak)) void app_malloc_failed_hook(void)
{
    for (;;)
        ;
}
#endif

__attribute__((weak)) void heap_lock(void)
{
}

__attribute__((weak)) void heap_unlock(void)
{
}

/*-----------------------------------------------------------*/

static void insert_block_into_free_list( block_link_t * block_to_insert );

/*-----------------------------------------------------------*/

static const size_t heap_struct_size = ( sizeof( block_link_t ) + ( ( size_t ) ( BYTE_ALIGNMENT - 1 ) ) ) & ~( ( size_t ) BYTE_ALIGNMENT_MASK );

static block_link_t start, * end = NULL;

static size_t free_bytes_remaining = 0U;
static size_t minimum_ever_free_bytes_remaining = 0U;
static size_t number_of_successful_allocations = 0;
static size_t number_of_successful_free = 0;

static size_t block_allocate_bit = 0;

/*-----------------------------------------------------------*/

void * pt_malloc( size_t size )
{
    block_link_t * block, * previous_block, * new_block_link;
    void * ret = NULL;

    /* The heap must be initialised before the first call to
     * prvPortMalloc(). */
    HEAP_ASSERT( end );

    heap_lock();
    {
        if( ( size & block_allocate_bit ) == 0 )
        {
            /* The wanted size is increased so it can contain a block_link_t
             * structure in addition to the requested amount of bytes. */
            if( ( size > 0 ) && 
                ( ( size + heap_struct_size ) >  size ) ) /* Overflow check */
            {
                size += heap_struct_size;

                /* Ensure that blocks are always aligned 
                *   请求分配的区域 不是字节对齐的 ，计算得到一个字节对齐的大小
                */
                if( ( size & BYTE_ALIGNMENT_MASK ) != 0x00 )
                {
                    /* Byte alignment required. Check for overflow */
                    if( ( size + ( BYTE_ALIGNMENT - ( size & BYTE_ALIGNMENT_MASK ) ) ) >
                         size )
                    {
                        size += ( BYTE_ALIGNMENT - ( size & BYTE_ALIGNMENT_MASK ) );
                    } 
                    else 
                    {
                        size = 0;
                    }
                }
            }
            else
            {
                size = 0;
            }

            if( ( size > 0 ) && ( size <= free_bytes_remaining ) )
            {
                /* Traverse the list from the start	(lowest address) block until
                 * one of adequate size is found. */
                previous_block = &start;
                block = start.next_free_block;

                while( ( block->block_size < size ) && ( block->next_free_block != NULL ) )
                {
                    previous_block = block;
                    block = block->next_free_block;
                }

                /* If the end marker was reached then a block of adequate size
                 * was not found. */
                if( block != end )
                {
                    /* Return the memory space pointed to - jumping over the
                     * block_link_t structure at its start. */
                    ret = ( void * ) ( ( ( uint8_t * ) previous_block->next_free_block ) + heap_struct_size );

                    /* This block is being returned for use so must be taken out
                     * of the list of free blocks. */
                    previous_block->next_free_block = block->next_free_block;

                    /* If the block is larger than required it can be split into
                     * two. */
                    if( ( block->block_size - size ) > MINIMUM_BLOCK_SIZE )
                    {
                        /* This block is to be split into two.  Create a new
                         * block following the number of bytes requested. The void
                         * cast is used to prevent byte alignment warnings from the
                         * compiler. */
                        new_block_link = ( void * ) ( ( ( uint8_t * ) block ) + size );

                        /* Calculate the sizes of two blocks split from the
                         * single block. */
                        new_block_link->block_size = block->block_size - size;
                        block->block_size = size;

                        /* Insert the new block into the list of free blocks. */
                        insert_block_into_free_list( ( new_block_link ) );
                    }

                    free_bytes_remaining -= block->block_size;

                    if( free_bytes_remaining < minimum_ever_free_bytes_remaining )
                    {
                        minimum_ever_free_bytes_remaining = free_bytes_remaining;
                    }

                    /* The block is being returned - it is allocated and owned
                     * by the application and has no "next" block. */
                    block->block_size |= block_allocate_bit;
                    block->next_free_block = NULL;
                    number_of_successful_allocations++;
                }
            }
        }
    }
    ( void ) heap_unlock();

    #if ( USE_MALLOC_FAILED_HOOK == 1 )
    {
        if ( ret == NULL ) {
            app_malloc_failed_hook();
        }
    }
    #endif /* if ( USE_MALLOC_FAILED_HOOK == 1 ) */

    return ret;
}
/*-----------------------------------------------------------*/

void pt_free( void * pv )
{
    uint8_t * puc = ( uint8_t * ) pv;
    block_link_t * link;

    if( pv != NULL )
    {
        /* The memory being freed will have an block_link_t structure immediately
         * before it. */
        puc -= heap_struct_size;

        /* This casting is to keep the compiler from issuing warnings. */
        link = ( void * ) puc;

        /* Check the block is actually allocated. */
        HEAP_ASSERT( ( link->block_size & block_allocate_bit ) != 0 );
        HEAP_ASSERT( link->next_free_block == NULL );

        if( ( link->block_size & block_allocate_bit ) != 0 )
        {
            if( link->next_free_block == NULL )
            {
                /* The block is being returned to the heap - it is no longer
                 * allocated. */
                link->block_size &= ~block_allocate_bit;

                heap_lock();
                {
                    /* Add this block to the list of free blocks. */
                    free_bytes_remaining += link->block_size;
                    insert_block_into_free_list( ( ( block_link_t * ) link ) );
                    number_of_successful_free++;
                }
                ( void ) heap_unlock();
            }
        }
    }
}
/*-----------------------------------------------------------*/

size_t pt_get_free_size( void )
{
    return free_bytes_remaining;
}
/*-----------------------------------------------------------*/

size_t pt_get_min_ever_free_heap_size( void )
{
    return minimum_ever_free_bytes_remaining;
}
/*-----------------------------------------------------------*/

static void insert_block_into_free_list( block_link_t * block_to_insert )
{
    block_link_t * iterator;
    uint8_t * puc;

    /* Iterate through the list until a block is found that has a higher address
     * than the block being inserted. */
    for( iterator = &start; iterator->next_free_block < block_to_insert; iterator = iterator->next_free_block )
    {
        /* Nothing to do here, just iterate to the right position. */
    }

    /* Do the block being inserted, and the block it is being inserted after
     * make a contiguous block of memory? */
    puc = ( uint8_t * ) iterator;

    if( ( puc + iterator->block_size ) == ( uint8_t * ) block_to_insert )
    {
        iterator->block_size += block_to_insert->block_size;
        block_to_insert = iterator;
    }

    /* Do the block being inserted, and the block it is being inserted before
     * make a contiguous block of memory? */
    puc = ( uint8_t * ) block_to_insert;

    if( ( puc + block_to_insert->block_size ) == ( uint8_t * ) iterator->next_free_block )
    {
        if( iterator->next_free_block != end )
        {
            /* Form one big block from the two blocks. */
            block_to_insert->block_size += iterator->next_free_block->block_size;
            block_to_insert->next_free_block = iterator->next_free_block->next_free_block;
        }
        else
        {
            block_to_insert->next_free_block = end;
        }
    }
    else
    {
        block_to_insert->next_free_block = iterator->next_free_block;
    }

    /* If the block being inserted plugged a gab, so was merged with the block
     * before and the block after, then it's next_free_block pointer will have
     * already been set, and should not be set here as that would make it point
     * to itself. */
    if( iterator != block_to_insert )
    {
        iterator->next_free_block = block_to_insert;
    }
}
/*-----------------------------------------------------------*/

void pt_heap_region( const pt_heap_region_t * const heap_regions )
{
    block_link_t * first_free_block_in_region = NULL, * previous_free_block;
    size_t aligned_heap;
    size_t total_region_size, total_heap_size = 0;
    long defined_regions = 0;
    size_t address;
    const pt_heap_region_t * heap_region;

    /* Can only call once! */
    HEAP_ASSERT( end == NULL );

    heap_region = &( heap_regions[ defined_regions ] );

    while( heap_region->size_in_bytes > 0 )
    {
        total_region_size = heap_region->size_in_bytes;

        /* Ensure the heap region starts on a correctly aligned boundary.
         * 从第一个堆空间节点 取出地址
         */
        address = ( size_t ) heap_region->stat_address;

        /* 将这个地址修改为字节对齐的地址，并计算可用堆空间的大小 */
        if( ( address & BYTE_ALIGNMENT_MASK ) != 0 )
        {
            address += ( BYTE_ALIGNMENT - 1 );
            address &= ~BYTE_ALIGNMENT_MASK;

            /* Adjust the size for the bytes lost to alignment. */
            total_region_size -= address - ( size_t ) heap_region->stat_address;
        }

        aligned_heap = address;

        /* Set start if it has not already been set. 
        *  第一次循环，设置start节点指向的位置
        */
        if( defined_regions == 0 )
        {
            /* start is used to hold a pointer to the first item in the list of
             *  free blocks.  The void cast is used to prevent compiler warnings. */
            start.next_free_block = ( block_link_t * ) aligned_heap;
            start.block_size = ( size_t ) 0;
        }
        else
        {
            /* Should only get here if one region has already been added to the
             * heap. 
             * 当一个区域已经添加到堆后，才能走到这里。从第二次循环以后。
             */
            HEAP_ASSERT( end != NULL );

            /* Check blocks are passed in with increasing start addresses. 
            *  检查块是以递增的起始地址传入，end是前一块区域的结束位置，则当前的addr必须大于end
            */
            HEAP_ASSERT( address > ( size_t ) end );
        }

        /* Remember the location of the end marker in the previous region, if
         * any. 
         * 记录前一个区域结束的位置
         */
        previous_free_block = end;

        /* end is used to mark the end of the list of free blocks and is
         * inserted at the end of the region space. 
         * 计算当前空闲块的结束地址，并把这个地址传给end节点
         */
        address = aligned_heap + total_region_size;
        address -= heap_struct_size;
        address &= ~BYTE_ALIGNMENT_MASK;
        end = ( block_link_t * ) address;
        end->block_size = 0;
        end->next_free_block = NULL;

        /* To start with there is a single free block in this region that is
         * sized to take up the entire heap region minus the space taken by the
         * free block structure. 
         * 把这块区域的开头位置，写上block_link_t的数据信息，可以根据信息找到下一个end节点
         * */
        first_free_block_in_region = ( block_link_t * ) aligned_heap;
        first_free_block_in_region->block_size = address - ( size_t ) first_free_block_in_region;
        first_free_block_in_region->next_free_block = end;

        /* If this is not the first region that makes up the entire heap space
         * then link the previous region to this region. 
         * 如果这不是第一块区域，则把前一块区域的end节点连接到当前这块区域上
         */
        if( previous_free_block != NULL )
        {
            previous_free_block->next_free_block = first_free_block_in_region;
        }

        /* 计算总区域大小 */
        total_heap_size += first_free_block_in_region->block_size;

        /* Move onto the next pt_heap_region_t structure. 
         * 移动区域到下一个位置
         */
        defined_regions++;
        heap_region = &( heap_regions[ defined_regions ] );
    }

    minimum_ever_free_bytes_remaining = total_heap_size;
    free_bytes_remaining = total_heap_size;

    /* Check something was actually defined before it is accessed. */
    HEAP_ASSERT( total_heap_size );

    /* Work out the position of the top bit in a size_t variable. */
    block_allocate_bit = ( ( size_t ) 1 ) << ( ( sizeof( size_t ) * BITS_PER_BYTE ) - 1 );
}


#endif